#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void HeapInit(Heap* php)//初始化堆
{
    assert(php);
    php->array = NULL;
    php->size = php->capacity = 0;
}

void HeapDestroy(Heap* php) //堆的销毁
{
    assert(php);
    free(php->array);
    php->capacity = php->size = 0;
}

void HeapPrint(Heap* php) //堆的打印
{
    for (int i = 0; i < php->size; i++) 
    {
        printf("%d ", php->array[i]);
    }
    printf("\n");
}

bool HeapEmpty(Heap* php)//判断堆是否为空
{
    assert(php);

    return php->size == 0; // 如果为size为0则表示堆为空
}


HPDataType HeapTop(Heap* php) //返回堆顶数据
{
    assert(php);
    assert(!HeapEmpty(php));

    return php->array[0];
}

int HeapSize(Heap* php) //统计堆的个数
{
    assert(php);

    return php->size;
}

void HeapCheckCapacity(Heap* php) //检查容量  写过很多次了
{
    if (php->size == php->capacity) 
    {
        int newCapacity = php->capacity == 0 ? 4 : (php->capacity * 2); //第一次给4，其他情况扩2倍
        HPDataType* tmpArray = (HPDataType*)realloc(php->array, sizeof(HPDataType) * newCapacity); // 数组扩容
        if (tmpArray == NULL)
        {  //检查realloc
            printf("realloc failed!\n");
            exit(-1);
        }
        //更新他们的大小
        php->array = tmpArray;
        php->capacity = newCapacity;
    }
}

void Swap(HPDataType* px, HPDataType* py) //交换函数
{
    HPDataType tmp = *px;
    *px = *py;
    *py = tmp;
}

void BigAdjustUp(int* arr, int child) //大根堆上调
{
    assert(arr);
    // 首先根据公式计算算出父亲的下标
    int parent = (child - 1) / 2;
    // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0）
    while (child > 0) //不能写parent >= 0
    {                 //为什么呢？最后一次往上走时，
                     //child = parent;  此时child = 0
                     //parent = (child - 1) / 2;
                     //(0 - 1) / 2 = 0  这么一来parent仍然会是0
                     //导致parent根本就不会小于0
        if (arr[child] > arr[parent]) // 如果孩子大于父亲（不符合大堆的性质）
        {  
            // 交换他们的值
            Swap(&arr[child], &arr[parent]);
            // 往上走
            child = parent;
            parent = (child - 1) / 2;
        }
        else// 如果孩子小于父亲（符合堆的性质）
        {  
            break;// 跳出循环
        }
    }
}

void SmallAdjustUp(int* arr, int child) //小堆上调
{
    assert(arr);
    // 首先根据公式计算算出父亲的下标
    int parent = (child - 1) / 2;
    // 最坏情况:调到根，child=parent 当child为根节点时结束（根节点永远是0）
    while (child > 0)
    {
        if (arr[child] < arr[parent])  // 如果孩子小于父亲（不符合小堆的性质）
        { 
            Swap(&arr[child], &arr[parent]);
            // 往上走
            child = parent;
            parent = (child - 1) / 2;
        }
        else  // 如果孩子小于父亲（符合堆的性质）
        {  
            break;
        }
    }
}

void HeapPush(Heap* php, HPDataType x) 
{
    assert(php);
    // 检查是否需要扩容
    HeapCheckCapacity(php);
    // 插入数据
    php->array[php->size] = x;
    php->size++;
    // 向上调整 [目标数组，调整位置的起始位置（刚插入的数据）]
    BigAdjustUp(php->array, php->size - 1);
}


//小根堆下调  左右子树为小根堆，根节点不满足时使用  左右子树不满足就对其进行下调
void SmallAdjustDown(int* arr, int n, int parent) 
{
    int child = parent * 2 + 1; // 默认为左孩子
    while (child < n) // 叶子内
    { 
        // 选出左右孩子中小的那一个
        if (child + 1 < n && arr[child + 1] < arr[child]) //左孩子+1为右孩子
        {    //如果 child + 1 比 n 大，就说明没有右孩子，默认是对的
            child++;//左孩子+1更新为右孩子
        }
        if (arr[child] < arr[parent])// 如果孩子小于父亲（不符合小堆的性质）
        { 
            // 交换它们的值
            Swap(&arr[child], &arr[parent]);
            // 往下走
            parent = child;
            child = parent * 2 + 1;
        }
        else // 如果孩子大于父亲（符合小堆的性质）
        { 
            break;
        }
    }
}

void BigAdjustDown(int* arr, int n, int parent) //大根堆下调
{
    int child = parent * 2 + 1; // 默认为左孩子
    while (child < n) // 叶子内
    { 
        // 选出左右孩子中大的那一个
        if (child + 1 < n && arr[child + 1] > arr[child]) 
        {
            child++;
        }
        if (arr[child] > arr[parent]) { // 如果孩子大于父亲（不符合大堆的性质）
            // 交换它们的值
            Swap(&arr[child], &arr[parent]);
            // 往下走
            parent = child;
            child = parent * 2 + 1;
        }
        else  // 如果孩子小于父亲（符合大堆的性质）
        {
            break;
        }
    }
}

void HeapPop(Heap* php) 
{
    assert(php);
    assert(!HeapEmpty(php));
    // 删除数据
    Swap(&php->array[0], &php->array[php->size - 1]);
    php->size--;
    // 向下调整 [目标数组，数组的大小，调整位置的起始位置]
    //SmallAdjustDown(php->array, php->size, 0);
    BigAdjustDown(php->array, php->size, 0);
}